1. Field of the Invention
The present invention relates to a hybrid cost reduction technique for test point selection for scan-based built-in self-testing (BIST) of a sequential circuit.
2. Description of the Related Art
Integrated circuits (IC) are tested to ensure that the component is defect-free after being manufactured and/or remains in proper working condition during use. Testing of the IC may be accomplished by applying a test pattern to stimulate the inputs of a circuit and monitoring the output response to detect the occurrence of faults. The test patterns may be applied to the circuit using an external testing device. Alternatively, the pattern generator may be a BIST structure comprising part of the internal circuitry in the IC which generates the test patterns.
Although it is desirable when testing the logic circuit to use exhaustive testing by checking the circuit output response to all 2.sup.n possible input permutations, this approach becomes impracticable as the number of input variables n increases. Thus, a related technique, referred to as pseudo-random testing, is employed when the number of input variables is so large that it becomes impracticable to use an exhaustive testing approach. Pseudo-random testing is an alternative technique that generates test patterns in a random fashion from the 2.sup.n possible patterns. In this approach fewer than all of the 2.sup.n patterns are tested. Because of the relatively low hardware overhead and the simplicity of test pattern generation, pseudo-random testing is a preferred technique for BIST. Practical circuits, however, often contain random pattern resistant faults which result in unacceptable low fault coverages for a reasonable test length. Under these circumstances the testability of the circuit may be improved by inserting test points into the circuit.
A conventional scan-based BIST structure is shown in FIG. 1 and disclosed in U.S. Pat. No. 5,329,533, which is herein incorporated by reference. In order to test a sequential circuit it must first be converted to either a full or partial-scan circuit. This conversion may be realized by replacing some or all of the flip-flops in the circuit under test with scan flip-flops and connecting the scan flip-flops into one or more scan chains. If all of the flip-flops are replaced, then the circuit under test is a full scan circuit and the network N is a combinational circuit. In a partial scan BIST scheme, only crucial flip-flops selected using a cycle-breaking algorithm, as for example described by Cheng and Agrawal, "A Partial Scan Method for Sequential Circuits with Feedback," IEEE Transactions on Computers, vol. 39, no. 4, pp. 544-548, April 1989, which is herein incorporated by reference, are replaced with scan flip flops and the network N is a near acyclic circuit (NAC), that is, a synchronous sequential circuit whose corresponding directed graph G does not contain any cycle with length greater than one.
As shown in FIG. 1, the scan-based BIST structure includes a test pattern generator 100 which supplies random patterns to primary inputs and, via scan chains, to pseudo-inputs (outputs of the scan flip-flops). The test pattern generator 100 includes a linear feedback shift register (LFSR) 110 and a phase shifter (PS) 120. Data from the primary outputs and, via the scan chain, from pseudo-outputs (inputs of the scan flip-flops) are compacted by an output data compactor (ODC) 130 such as a multiple input signature register (MISR) 140 and a space compactor (SC) 150.
To begin testing, the integrated circuit is placed in a test mode during which the bits of a test vector are scanned into the chain of scan flip-flops of the integrated circuit. After the test data is entered, the integrated circuit is returned to a non-test mode during which the scan flip-flops respond to the previously received test data in their usual manner. A predetermined period of time later, the test mode is reentered and the output response to the scan flip-flops is captured.
One or more test points, e.g. control points and/or observation points, may be inserted into the circuit under test to improve the fault coverage. An observation point is inserted at a node to improve the observabilities of the node and all other nodes that directly/indirectly feed the node. The effect of inserting an observation point on the circuit under test 160 is represented by the hatched region in FIG. 2a. FIGS. 2b and 2c illustrate the circuit before and after insertion of the observation point. As is clearly evident from a comparison of FIGS. 2b and 2c, an observation point is implemented by connecting the node to the ODC.
A control point may be inserted at a node to improve controllabilities as well as observabilites of nodes in a circuit. Changing the controllability of a node inherently also changes the controllabilities of nodes influenced by the node as indicated by the shaded region in FIG. 3a. In addition, the observabilites of nodes in the hatched area of FIG. 3a, which includes the shaded region, are altered. FIGS. 3b and 3c illustrate the circuit before and after insertion of a control point. The added gate G in FIG. 3c is either an OR gate (1-control point) or an AND gate (0-control point). Signal t is connected to a random source whose 1-controllability (defined as the probability of having a logic value "1") is 0.5 at the BIST mode. During the normal mode, 1-controllability of signal t is 0 for a 1-control point and 1 for a 0-control point. If the 1-controllability of s is too small, an OR gate is inserted such that during the BIST mode the 1-controllability s' is higher than 0.5. On the other hand, if the 1-controllability of s is too large, an AND gate is added such that the 1-controllability of s' is smaller than 0.5. Regardless of which gate is added, the observabilities of all the nodes that affect s are reduced and, in the worst case is reduced by approximately one half.
Fault simulation is one method of selecting test points by identifying the reconvergent fanout points and gates which block the activation and propagation of faults. These points and gates are classified as good test point candidates. However, fault simulation is costly If in terms of computational complexity and hence, is not practical for relatively large circuits.
An alternative approach is to use testability measures to select test points, as for example controllability/observability programs (COP), as described by F. Brglez, "On Testability of Combinational Networks," Proc. of International Symposium on Circuits and Systems, pp. 221-225, May 1984, which is herein incorporated by reference. COP is a well known procedure to estimate the 1-controllability C.sub.s and observability O.sub.s of every signal s in a combinational network. The variable C.sub.s represents the probability that node s has a logic value "1"; whereas O.sub.s represents the probability that the logic value at node s can be observed via at least one of the primary outputs. The variables C.sub.s and O.sub.s are calculated by sweeping the circuit once. Controllabilities and observabilities themselves are not sufficient to determine the selection of test points, however, because they represent a local testability impact rather than a global testability impact due to the insertion of a test point.
R. Lisanke et al., "Testability-Driven Random Test Pattern Generation," IEEE Tran. on computer-Aided Design, vol. CAD-6, pp. 1082-1087, November 1987, which is herein incorporated by reference, defines a cost function U that is used to estimate the global circuit testability ##EQU1##
where F is the fault set; PA1 .vertline.F.vertline. is the cardinality of F; and PA1 Pd.sub.i is the detection probability of fault i. PA1 U.sup.org and U.sup.s are the values of the cost function U, before and after insertion of the test point candidate s, respectively; and PA1 Pd.sub.i.sup.org and Pd.sub.i.sup.s are the detection probabilities of fault i before and after insertion of the test point s, respectively.
For the stuck-at-fault model, Pd.sub.i may be expressed as one of the following two equations: EQU Pd.sub.s/0 =C.sub.s.multidot.O.sub.s, for stuck-at-0 fault at s EQU Pd.sub.s/1 =(1-C.sub.s).multidot.0.sub.s, for stuck-at-1 fault at s
In the cost function equation above 1/Pd.sub.i represents the expected number of pseudo-random patterns needed to be applied to detect fault i. Thus, the cost factor U is an indicator of circuit testability and the objective of test point insertion is to minimize the value U. The value of the cost function U changes once a test point is added and the difference between the cost function values before and after insertion of a test point s is referred to as the actual cost reduction (ACR). Given a fault set F, the ACR for a test point candidate s is defined as ##EQU2##
where
In short, ACR is the average expected test length after inserting the test point s into a circuit. The objective of test point selection is to select a test point that produces the largest ACR. One exhaustive method for selecting a test point is to compute ACR for each possible test point candidate in the circuit. As is readily apparent, the computational complexity when testing relatively large circuits makes this exhaustive approach impracticable.
In addition, ACR calculation results using this method are not perfect indicators for selecting test points in that COP provides only an estimate of true controllability and observability because Pd.sub.i assumes that controllability and observability are independent which is not always true. Testing has shown, however, that the ACRs computed using this technique are sufficiently accurate for relatively large circuits to serve as a reference point for verifying the accuracy of other techniques.
To reduce the complexity of calculating the ACR for every point Seiss, B., Trouborst, P., and Schalz, M., in "Test Point Insertion for Scan-Based BIST", Proceedings of International Test Conference, pp. 253-262, April 1989, which is herein incorporated by reference, developed an algorithm that calculates a cost reduction function (CRF) to estimate the reduction of the cost function U due to the insertion of a test point. FIG. 4 is a flow chart of this prior art CRF-based algorithm. At each iteration, CRFs are calculated for every node in the circuit in step 410 from which a relatively small set of potentially good candidates is selected in step 415. Then in step 420 the ACR for every candidate in the set is evaluated and the candidate with the largest ACR value is chosen as the test point in step 425. This iterative process stops when in step 400 the number of test points selected reaches a predetermined user specified limit.
The CRF of all nodes in the circuit may be computed in linear time based on the controllability gradient Gc.sub.s and observability gradient Go.sub.s of the cost function U defined as EQU Gc.sub.s =.differential.U/.differential.C.sub.s EQU Go.sub.s =.differential.U/.differential.O.sub.s
The gradients Gc.sub.s and Go.sub.s represent the change rates of the cost function U with respect to an infinitely small change of controllability C.sub.s and observability O.sub.s, respectively. Cost function gradient values for all nodes in a circuit may be computed in linear time using the algorithms developed by Lisanke.
Although the CRFs may be computed efficiently these estimated values can deviate significantly from ACRs, especially when the circuit reaches a relatively high fault coverage, for several reasons. First, observability changes as a result of insertion of a control point are completely ignored. The observability changes of nodes in the fanin cone of primary outputs reachable from the control point (hatched and shaded regions in FIG. 3a) are neglected. Second, certain circuit structures and fault sets are assumed during the derivation of the CRF equations. Faults associated with a chain of AND gates or OR gates generally have extremely low detection probabilities and, thus are classified as hard-to-detect faults. By assuming the circuit under test will have these types of structures and associated hard-to-detect faults, the controllability value C.sub.s can be factored out of the CRF equations such that the rest of the terms in the cost function U are independent of C.sub.s. This assumption is not typically satisfied in practical circuits and thus, often contributes to errors in the CRFs. The cumulative effects of both of these assumptions may increase the inaccuracy of the CRFs even more.
As a result of the inaccuracy of the CRFs, the test point candidate with the largest CRF generally does not have the largest ACR. Therefore, the CRF-based algorithm explicitly computes ACRs for a set of candidates with relative large CRFs so as not to exclude a test point candidate having the largest ACR but not necessarily the largest CRF. Several constraints must be balanced when determining the set of candidates. On the one hand, since usage of the central processing unit is dominated during calculation of ACRs using the prior art CRF-based algorithm, a relatively large candidate set results in relatively high computational complexity. On the other hand, if the selected candidate size is relatively small, some good test point candidates may be excluded. In summary, the overall performance of the CRF-base algorithm is sensitive to the candidate size set chosen.
Thus, it is desirable to develop a method for efficiently and accurately estimating the ACR values for test point selection in a scan-based BIST architecture so as to reduce the number of nodes in the circuit for which the ACR must be explicitly calculated.